1. Field of the Invention
The present invention relates generally to virtual memory systems for multitasking computer systems and particularly to methods and systems for efficiently retrieving pages of memory from secondary memory storage.
2. Summary of the Prior Art
Referring to FIG. 1, a computer system 10 is illustrated. The computer system is comprised of a central processing unit (hereinafter "CPU") 20, a plurality of processes 22-30 and primary memory 32, secondary memory 34 and a memory manager 36. Directly connected to the CPU 20 is the primary memory 32. The primary memory 32 is a high speed random access memory. It facilitates CPU processing by permitting fast memory access times. Secondary memory, on the other hand, is usually a large, relatively slow memory device. For example, magnetic disc drives are frequently used as secondary memory. Secondary memory is generally characterized by a slow access time and being relatively inexpensive, compared to primary memory.
In the computer system 10, secondary memory 34 is much larger than primary memory 32. Each process 22-30 performs operations using primary memory 32 which is the only memory that a process "sees." Additional memory is located in the secondary memory and when that information is needed it is transferred into primary memory for the requesting process to access. Since primary memory is small, relative to secondary memory, information is constantly swapped in and out of primary memory. The device which controls the transfer of data between primary and secondary memory is called a virtual memory manager 36 (hereinafter sometimes called "memory manager"). The memory manager 36 utilizes a virtual memory scheme.
Many virtual memory schemes are used in the prior art. An example of one is now illustrated. In FIG. 1, a computer system 10 concurrently runs several processes 22-30 using the CPU 20. Each of these processes 22-30 is allocated a certain portion of primary memory 32. More specifically, each process has a virtual memory space which may far exceed the amount of primary memory that is assigned to it. The portion of each virtual memory space which is currently stored in primary memory is specified by a "working set" list 22a-30a which is maintained for each process. Thus each process has a "working set," and all other data for the process is stored in a secondary memory 34.
The virtual memory manager 36 controls which portions of each process's virtual memory space is to be stored in primary memory and dynamically changes the allocation of primary memory as required.
Referring to FIG. 2, in a virtual memory system, both physical and virtual memory spaces are divided into equally sized "pages." The memory manager 36 (shown in FIG. 1) keeps track of the pages for each process running in the computer 10 by using a table called a "page table" 38. The page table 38 for any one process 22 contains many "page table entries" in (PTEs) 42, each of which specifies the location and status of one page in the process's virtual memory space.
Since a process typically uses many pages of memory, there will be a corresponding number of PTEs 42. These PTEs are stored in an array (i.e., table) which itself occupies multiple pages of memory. For example, a process might use four thousand pages of memory and the four thousand PTEs might occupy four pages. Each page used to store PTEs is called a "page table page" 40 (hereinafter "PTP").
When a page of data is requested by a process and that page is not in primary memory 32, the memory manager 36 finds that page in secondary memory and copies it into primary memory 32. Often, when a page in secondary memory is requested by a process 22, logically contiguous pages will subsequently be requested. To improve the efficiency of swapping in pages from secondary memory, a "cluster" of logically contiguous pages are read into primary memory along with the requested page.
In-page clustering can sometimes be inefficient because the additional pages read in may not be used by the process. It has been found by the inventors that the optimal size of in-page clusters tends to be different in different parts of a process's virtual memory space. In many instances, a process will sequentially access logically contiguous pages in certain portions of its virtual memory space, but will access pages in a more random fashion in other portions of its virtual memory space.
The present invention makes in-page clustering more efficient by providing a system and method for heuristic modification of the number of cluster pages brought into primary memory. Cluster sizes are heuristically adjusted for different regions of a process's virtual memory space in accordance with the memory usage patterns of the process.